package com.jiang.专题.动态规划.Q2466;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/01/05 21:19
 */
class Solution {
    // final int MOD = 1_000_000_007;

    // 动态规划 + 记忆化搜索
    // public int countGoodStrings(int low, int high, int zero, int one) {
    //     int[] dp = new int [high + 1]; // dp[i] 表示字符串长度为i时有几种情况
    //     Arrays.fill(dp, -1); // 表示未计算
    //     int res = 0;
    //     for (int i = low; i <= high; i++) {
    //         res = (res + dfs(i, zero, one, dp)) % MOD;
    //     }
    //     return res;
    // }

    // public int dfs(int i, int zero, int one, int[] dp) {
    //     if (i < 0) return 0;
    //     if (i == 0) return 1; // dfs (i, zero, one, dp), i - zero == 0 或 i - one == 0

    //     if (dp[i] != -1) return dp[i];

    //     return dp[i] = (dfs(i - zero, zero, one, dp) + dfs(i - one, zero, one, dp)) % MOD;
    // }

    // 递推 + 动态规划
    public int countGoodStrings(int low, int high, int zero, int one) {
        final int MOD = (int) 1e9 + 7;
        int[] dp = new int [high + 1]; // dp[i] 表示字符串长度为i时有几种情况
        dp[0] = 1;
        int res = 0;
        for (int i = 1; i <= high; i++) {
            if (i >= zero) dp[i] = dp[i - zero];
            if (i >= one) dp[i] = (dp[i] + dp[i - one]) % MOD;
            if (i >= low) res = (res + dp[i]) % MOD;
        }
        return res;
    }
}
